namespace AdvancedTraining.Lesson51;

/// <summary>
/// 珂珂吃香蕉问题 - LeetCode 875
/// 使用二分查找计算珂珂在H小时内吃完所有香蕉的最小速度
/// </summary>
public class KokoEatingBananas //leetcode_0875
{
    /// <summary>
    /// 计算珂珂在H小时内吃完所有香蕉的最小速度
    /// 算法思路：二分查找
    /// 1. 速度的范围是[1, max(piles)]
    /// 2. 对于每个速度，计算吃完所有香蕉需要的时间
    /// 3. 如果时间小于等于H，说明速度足够，尝试更小的速度
    /// 4. 如果时间大于H，说明速度不够，尝试更大的速度
    /// 5. 找到满足条件的最小速度
    /// 时间复杂度：O(N * logM)，其中N为piles长度，M为max(piles)
    /// 空间复杂度：O(1)
    /// </summary>
    /// <param name="piles">香蕉堆数组，piles[i]表示第i堆香蕉的数量</param>
    /// <param name="h">小时数，珂珂必须在H小时内吃完所有香蕉</param>
    /// <returns>最小吃香蕉速度（根/小时）</returns>
    public static int MinEatingSpeed(int[] piles, int h)
    {
        var l = 1;
        var r = 0;
        foreach (var pile in piles) r = Math.Max(r, pile);
        var ans = 0;
        while (l <= r)
        {
            var m = l + ((r - l) >> 1);
            if (Hours(piles, m) <= h)
            {
                ans = m;
                r = m - 1;
            }
            else
            {
                l = m + 1;
            }
        }

        return ans;
    }

    /// <summary>
    /// 计算以给定速度吃完所有香蕉需要的小时数
    /// 对于每一堆香蕉，需要 (pile + speed - 1) / speed 小时
    /// 这相当于向上取整：Math.Ceiling((double)pile / speed)
    /// </summary>
    /// <param name="piles">香蕉堆数组</param>
    /// <param name="speed">吃香蕉速度（根/小时）</param>
    /// <returns>吃完所有香蕉需要的小时数</returns>
    private static long Hours(int[] piles, int speed)
    {
        long ans = 0;
        var offset = speed - 1;
        foreach (var pile in piles) ans += (pile + offset) / speed;
        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 珂珂吃香蕉问题测试 ===");

        // 测试用例1: LeetCode官方示例
        Test1();

        // 测试用例2: 大数堆，长时间
        Test2();

        // 测试用例3: 一堆香蕉
        Test3();

        // 测试用例4: 每小时只能吃一根
        Test4();

        // 测试用例5: 正好吃完
        Test5();

        // 测试用例6: 边界情况
        Test6();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("二分查找：速度范围在[1, max(pipes)]内查找最小满足条件的速度");
        Console.WriteLine("时间计算：每堆香蕉需要向上取整的小时数");
        Console.WriteLine("时间复杂度：O(N * logM)，N为堆数，M为最大堆大小");
        Console.WriteLine("空间复杂度：O(1)");
    }

    /// <summary>
    /// 测试用例1: LeetCode官方示例
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: LeetCode官方示例");
        int[] piles = [3, 6, 7, 11];
        int h = 8;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 4)");
    }

    /// <summary>
    /// 测试用例2: 大数堆，长时间
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: 大数堆，长时间");
        int[] piles = [30, 11, 23, 4, 20];
        int h = 5;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 30)");
    }

    /// <summary>
    /// 测试用例3: 一堆香蕉
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 一堆香蕉");
        int[] piles = [30];
        int h = 15;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 2)");
    }

    /// <summary>
    /// 测试用例4: 每小时只能吃一根
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 每小时只能吃一根");
        int[] piles = [1, 1, 1, 1];
        int h = 4;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 1)");
    }

    /// <summary>
    /// 测试用例5: 正好吃完
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 正好吃完");
        int[] piles = [5, 5, 5, 5];
        int h = 4;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 5)");
    }

    /// <summary>
    /// 测试用例6: 边界情况 - 超大数堆，超长时间
    /// </summary>
    private static void Test6()
    {
        Console.WriteLine("\n测试用例6: 边界情况 - 超大数堆，超长时间");
        int[] piles = [805306368, 805306368, 805306368];
        int h = 1000000000;
        var result = MinEatingSpeed(piles, h);
        Console.WriteLine($"香蕉堆: [{string.Join(", ", piles)}]");
        Console.WriteLine($"小时数: {h}");
        Console.WriteLine($"最小速度: {result} (期望: 3)");
    }
}